La Macchina di Turing è un modello computazionale astratto, fondamentale in informatica teorica. Fu inventata da Alan Turing nel 1936. È utilizzata per definire il concetto di algoritmo e calcolabilità.
Componenti Principali:
Nastro Infinito: Un nastro infinito diviso in celle, ognuna contenente un simbolo di un alfabeto finito. Questo nastro funge da memoria della macchina.
Testina di Lettura/Scrittura: Una testina in grado di leggere il simbolo nella cella corrente, scrivere un nuovo simbolo nella cella, e spostarsi a destra o a sinistra sul nastro.
Stato: Un insieme finito di stati interni. La macchina si trova sempre in uno stato.
Funzioni di Transizione: Definiscono il comportamento della macchina. Data lo stato corrente e il simbolo letto, la funzione di transizione determina:
Funzionamento:
La macchina inizia in uno stato iniziale specifico. Ad ogni passo, la macchina legge il simbolo nella cella corrente del nastro. Basandosi sullo stato corrente e sul simbolo letto, la funzione di transizione determina le seguenti azioni:
Questo processo continua finché la macchina non raggiunge uno stato di accettazione o di rifiuto, oppure se entra in un ciclo infinito.
Importanza:
Definizione di Calcolabilità: La Macchina di Turing è usata come definizione formale di algoritmo. Una funzione è considerata calcolabile se e solo se esiste una Macchina di Turing in grado di calcolarla.
Universalità: Esistono Macchine di Turing universali (Macchina%20di%20Turing%20Universale) che possono simulare qualsiasi altra Macchina di Turing. Questo è un concetto fondamentale nell'informatica, alla base dell'idea di computer programmabili.
Limiti della Computazione: La Macchina di Turing è anche usata per dimostrare l'esistenza di problemi che non possono essere risolti da nessun algoritmo, come il problema%20dell'arresto (Halting Problem).
Formalizzazione:
Una macchina di Turing è formalmente definita come una 7-tupla:
M = (Q, Γ, b, Σ, δ, q0, F)
Dove:
Q è un insieme finito di stati.Γ è un alfabeto finito di simboli del nastro.b ∈ Γ è il simbolo di blank (cella vuota).Σ ⊆ Γ \ {b} è l'alfabeto di input.δ: Q × Γ → Q × Γ × {L, R} è la funzione di transizione, dove L indica lo spostamento a sinistra e R indica lo spostamento a destra.q0 ∈ Q è lo stato iniziale.F ⊆ Q è l'insieme degli stati finali (accettanti).La semplicità concettuale della Macchina di Turing, combinata con la sua potenza computazionale, la rende uno strumento essenziale per lo studio della calcolabilità e della complessità computazionale.